package first_practice;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: LeetCode-437-路径总和 III
 * @date 2025/4/17 16:08
 */
public class Solution437 {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> map = new HashMap<>(); // 存储前缀和及其出现的次数
        map.put(0L, 1);
        return dfs(map, root, 0, targetSum);
    }

    private int dfs(Map<Long, Integer> map, TreeNode root, long sum, int targetSum) {
        if (root == null)
            return 0;
        int ret = 0;
        sum += root.val;
        ret = map.getOrDefault(sum - targetSum, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
        ret += dfs(map, root.left, sum, targetSum);
        ret += dfs(map, root.right, sum, targetSum);
        map.put(sum, map.getOrDefault(sum, 0) - 1); // 同级左右节点之间没有路径
        return ret;
    }
}
